package main

import . "local/algorithm/util"

// ?stack不会因为导致后面步骤的改动对前面步骤的stack有影响吗？
func pathSum(root *TreeNode, sum int) [][]int {
	res := [][]int{}
	var findPath func(root *TreeNode, sum int, stack []int)
	findPath = func(root *TreeNode, sum int, stack []int) {
		if root == nil {
			return
		}

		stack = append(stack, root.Val)
		if root.Val == sum && root.Left == nil && root.Right == nil {
			//注意这里要复制，否则会出现后续步骤修改res中结果的情况出现
			res = append(res, append([]int{}, stack...))
			return
		}

		sum += root.Val
		findPath(root.Left, sum, stack)
		findPath(root.Right, sum, stack)
	}
	findPath(root, sum, []int{})
	return res
}
